package geekstudy.week2;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

/**
 *
 * 697. 数组的度
 * https://leetcode-cn.com/problems/degree-of-an-array/
 *
 * 执行结果： 通过 显示详情
 * 添加备注
 * 执行用时：39 ms, 在所有 Java 提交中击败了16.02% 的用户
 * 内存消耗：43.2 MB, 在所有 Java 提交中击败了23.14% 的用户
 *
 *
 */
public class Week2DegreeOfAnArray {

    public int findShortestSubArray(int[] nums) {

        Map<Integer, Integer> valueDegreeMap = new HashMap<Integer, Integer>(); // 定义每个值的度
        Map<Integer, Integer> valueFirstMap = new HashMap<Integer, Integer>(); // 定义每个值出现位置
        Map<Integer, Integer> valueEndMap = new HashMap<Integer, Integer>(); // 定义每个值最后位置
        // Set<Integer> degreeValueSet = new HashSet<Integer>();
        int maxDegree = 0; // 最大度

        for(int index = 0; index < nums.length; index++) {
            int value = nums[index];
            valueDegreeMap.put(value, valueDegreeMap.getOrDefault(value, 0) + 1);
            valueFirstMap.putIfAbsent(value, index);
            valueEndMap.put(value, index);
            int currentDegree = valueDegreeMap.get(value);
            if(currentDegree > maxDegree) {
                maxDegree = currentDegree;
            }
        }

        int shortestLength = nums.length; // 定义最短数组 和 数组本身长度一致
        // 取 度最大的 value, 最大度可能对应多个 value, 每个value的 shortest都不一样 需要取最小值
        for(Integer value : valueDegreeMap.keySet()) {
            if(valueDegreeMap.get(value) == maxDegree) {
                int length = valueEndMap.get(value) - valueFirstMap.get(value) + 1;
                shortestLength = Math.min(length, shortestLength);
            }
        }


        return shortestLength;
    }
}
